package org.algorithm.落雪.数组.三月.第四周;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhx
 * @date 2022-03-21 星期一18:26
 *
 * url: https://leetcode-cn.com/problems/pascals-triangle-ii/
 */
public class 杨辉三角II {

    public static void main(String[] args) {
        System.out.println(getRow2(3));
    }


    /**
     * 输入: rowIndex = 3
     * 输出: [1,3,3,1]
     *
     * 输入: rowIndex = 0
     * 输出: [1]
     *
     *
     * 输入: rowIndex = 1
     * 输出: [1,1]
     */
    public static List<Integer> getRow(int numRows) {

        List<Integer> temp = null;//上一行数据
        for (int i = 1; i <= numRows+1; i++) {
            List<Integer> list = new ArrayList<>();
            if (i == 1) {
                list.add(1);
            }else {
                list.add(0,1);
                list.add(list.size()-1,1);
            }
            //通过上一行数据计算当前行中间值
            for (int j = 1; j < i - 1; j++) {
                list.add(j,temp.get(j-1) + temp.get(j));
            }

            temp = list;
        }

        return temp;

    }

    public static List<Integer> getRow2(int numRows) {

        List<Integer> result = new ArrayList<>();
        result.add(1);
        for (int i = 1; i <= numRows; i++) {
            result.add(0);
            for (int j = i; j > 0; j--) {
                result.set(j, result.get(j) + result.get(j - 1));
            }
        }
        return result;
    }

}
